/**
 * https://leetcode.cn/submissions/detail/585421355/
 * 1443. 收集树上所有苹果的最少时间
 * Medium, 黄伟杰 2024.12.06
 * DFS
 */

class Solution
{
public:
    int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple)
    {
        vector<vector<int>> g(n);
        vector<bool> vis(n, false);
        for (auto e : edges)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        } // 图
        auto dfs = [&](auto dfs, int sta, int cost) -> int
        {
            if (vis[sta])
                return 0;
            vis[sta] = true;
            int childcost = 0;
            for (auto next : g[sta])
                childcost += dfs(dfs, next, 2); // cost为2是因为有来回,如果为0，就代表他的子节点没有苹果
            if (!hasApple[sta] && childcost == 0)
                return 0; // 自己和孩子都没苹果就不用经过
            return childcost + cost;
        };
        return dfs(dfs, 0, 0);
    }
};